/*
https://leetcode.cn/problems/pascals-triangle/submissions/584674373/?envType=problem-list-v2&envId=dynamic-programming
118. 杨辉三角
*/
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        if(numRows==1) return {{1}};
        vector<vector<int>>dp(numRows);
        for(int i=0;i<numRows;++i){
            for(int j=0;j<=i;++j){
            dp[i].push_back(0);
            }
        }
        for(int i=0;i<numRows;++i){
            dp[i][0]=1;
            dp[i][i]=1;
        }
        for(int i=2;i<numRows;++i){
            for(int j=1;j<i;++j){
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
            }
        }
        return dp;
    }
};